package com.zl.trappingrainwater;

// 10. 正则表达式匹配: https://leetcode.cn/problems/regular-expression-matching/description/
class RegularExpressionMatching {
    /**
     本题两个串匹配会出现的几种情况:
     s与p两个串匹配的过程中,
     注意: 当前暂时不讨论这两个串最终能否匹配成功，
     我们只尽可能最大程度去匹配会产生的情况.
     (也就是讨论匹配到不能再匹配的情况,并且保证最大限度的匹配)
     情况:
     1. s 剩余未能匹配的字符
     2. p 剩余未能匹配的字符

     分析:
     1. 如果 s 串还剩未能匹配的字符 说明一定匹配不成功
     2. 如果 p 串还剩未能匹配的字符 要分情况讨论
     1) 可能剩下类似于 (.*) (a-z*) (.*)
     这类常规字符或者单字符匹配字符后面紧接着*的组合
     并且可能存在若干个这种组合
     2) 不属于 1) 中讨论的情况那么就可以断定匹配不成功
     */

    /**
     * 暴力解 依赖下面f函数
     * @param s 主串
     * @param p 正则匹配串
     * @return 只要能匹配就返回true 否则返回false
     */
    public boolean isMatch(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        int n = s1.length;
        int m = p1.length;
        return f(s1,p1,n,m,0,0);
    }

    /**
     *
     * @param s 主串
     * @param p 正则匹配串
     * @param n 主串长度
     * @param m 匹配串长度
     * @param i 主串指针
     * @param j 匹配串指针
     * @return i位置及其往后 与 j位置及其往后 继续匹配 只要能匹配成功就返回true 否则false
     */
    public boolean f(char[] s, char[] p, int n, int m, int i, int j) {
        // base case
        // 定义黑盒之前就应该定义好这个黑盒在什么情况下算是匹配成功
        if (i == n && j == m) {
            // 当i指针和j指针同时都在两串末尾位置时,我们说就是匹配成功
            return true;
        }
        // base case
        // s 剩余未能匹配的字符
        if (j == m) {
            return false;
        }
        // 预判断当前 i指针与 j指针位置的字符能否进行常规匹配
        boolean cur = i < n && (p[j] == s[i] || p[j] == '.');
        // 判断当前字符是否与 * 组合
        boolean next = j < m-1 && p[j+1] == '*';
        /** 短路与前半部分：是否成立组合
         短路或前半部分: ~* 组合尝试匹配0个字符, 意味着组合结束匹配去到组合下一个字符
         短路或前半部分: ~* 组合尝试匹配1个字符 这里是当前尝试一个字符,
         而这里的组合还没有结束尝试,去到子问题可以继续尝试 */
        if (next && (f(s,p,n,m,i,j+2) || (cur && f(s,p,n,m,i+1,j)))) {
            return true;
        } else if (cur) { // 非 ~* 组合匹配, 必须保证主串还剩字符
            // 符合条件,两串统一去到下一个字符继续匹配
            return f(s,p,n,m,i+1,j+1);
        }
        return false;
    }


    /**
     * 动态规划
     * @param s 主串
     * @param p 正则匹配串
     * @return 只要能匹配就返回true 否则返回false
     */
    public boolean dp(String s, String p) {
        char[] s1 = s.toCharArray(), p1 = p.toCharArray();
        int n = s1.length, m = p1.length;
        boolean[][] dpT = new boolean[n+1][m+1];
        dpT[n][m] = true;
        for (int i = n;i >= 0;i--) {
            for (int j = m-1;j >= 0;j--) {
                boolean cur = i < n && (p1[j] == s1[i] || p1[j] == '.');
                boolean next = j < m-1 && p1[j+1] == '*';
                if (next && (dpT[i][j+2] || (cur && dpT[i+1][j]))) {
                    dpT[i][j] = true;
                } else if (cur) {
                    dpT[i][j] = dpT[i+1][j+1];
                }
            }
        }
        return dpT[0][0];
    }
}
